package h0802;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
  * @description 最大矩阵和
  * @author 不知名帅哥
  * @date 2024/8/2 22:42
  * @version 1.0
*/
public class MaxSubmatrixSum2 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n= sc.nextInt();
        int m=sc.nextInt();

        int[][] matrix=new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j]=sc.nextInt();
            }
        }
        System.out.println(getResult(n,m,matrix));
    }

    private static int getResult(int n, int m, int[][] matrix) {
        ArrayList<Integer> dp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            dp.add(maxSubArraySum(matrix[i])); //一行子矩阵最大和
            for (int j = i+1; j < n; j++) {
                //TODO copyOfRange 索引form-to 左闭右开
                // TODO 这里是先压缩（matrixZip），再进行计算最大子数组和。第一行;第一行第二行;第一二三行。
                //  至于筛选的过程，在maxSubArraySum方法中通过动态规划实现。双层for循环保证遍历所有情况。
                dp.add(maxSubArraySum(matrixZip(Arrays.copyOfRange(matrix,i,j+1))));
            }
        }

        //这里仅要求返回最大值。TODO 假如要求返回确定的最大子数组呢？ 答：
        return dp.stream().max((a,b)->a-b).orElse(0);

    }

    private static int[] matrixZip(int[][] matrix) {
       int cols=matrix[0].length;
       int rows=matrix.length;
       int[] zip=new int[cols];
        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                zip[i]+=matrix[j][i];
            }
        }
        return zip;
    }

    //TODO 这里是求矩阵一行最大子矩阵和。使用动态规划的方法。
    private static Integer maxSubArraySum(int[] nums) {
        int[] dp=new int[nums.length];
        int res= dp[0]=nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
            res=Math.max(res,dp[i]);
        }

        return res;
    }
}
